#include "main/utils.h"
using namespace std;

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
      vector<vector<int>> ans;
      int len = nums.size();
      sort(nums.begin(), nums.end());
      for (int first = 0; first < len; ++first) {
        if (first > 0 && nums[first] == nums[first - 1]) {
          continue;
        }
        int third = len - 1;
        for (int second = first + 1; second < third; ++second) {
          if (second > first + 1 && nums[second] == nums[second - 1]) {
            continue;
          }
          while (second < third && nums[second] + nums[third] > -nums[first]) {
            --third;
          }
          if (second == third) {
            break;
          }
          if (nums[second] + nums[third] == -nums[first]) {
            ans.push_back({nums[first], nums[second], nums[third]});
          }
        }
      }
      return ans;
    }
};

int main() {
  vector<int> input = {-1, 0, 1, 2, -1, -4};
  Solution su;
  auto output = su.threeSum(input);
  printVec("output", output);
}
